package algorithm.dynamicProgramming.leetcode;

import java.util.Arrays;

//55. 跳跃游戏
public class CanJump {
    public static void main(String[] args) {
        int[] data = {2,3,1,1,4};
        System.out.println(canJump22(data));
    }


    //动态规划
    public static boolean canJump(int[] nums) {

        int n = nums.length;
        boolean[] f = new boolean[n];
        f[0] = true;
        for (int i = 1; i < n; i++) {
            f[i] = false;
            for (int j = 0; j < i; j++) {
                if (f[j] && j + nums[j] >= i) {
                    f[i] = true;
                    break;
                }
            }
        }
        System.out.println(Arrays.toString(f));
        return f[n - 1];

    }

    //贪心算法
    public static boolean canJump12(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return true;
        }
        int max = nums[0]; //设定一个可以到大的最大坐标
        for (int i = 1; i < n; i++) {
            if (max >= i) {   //当前坐标可以到达
                max = Math.max(max, i + nums[i]);
                if (max >= n - 1) {
                    return true;
                }
            } else {
                break;
            }

        }
        return false;
    }


    //动态规划
    public static int canJump21(int[] nums) {

        int[] f = new int[nums.length];
        f[0] = 0;
        for (int i = 1; i < nums.length; i++) {
//            f[i] = nums.length+1;  //将数组填充上特别大的值
            f[i] = Integer.MAX_VALUE;  //将数组填充上特别大的值
        }

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] + j >= i) {
                    f[i] = Math.min(f[j] + 1, f[i]);
                }

            }
        }
        return f[nums.length - 1];

    }

    //贪心

    /**
     * 贪心算法：找能跳的最远的
     * 使用 k 记录目前能够跳到的最高位置
     * 使用 end 记录这次跳跃的边界，到达边界就跳跃次数 + 1
     *
     * @param nums
     * @return
     */
    public static int canJump22(int[] nums) {
        int k = 0; // 目前能跳到的最远位置
        int count = 0; // 跳跃次数
        int end = 0;  // 上次跳跃可达范围右边界（下次的最右起跳点）

        //这里有个小细节，因为是起跳的时候就 + 1 了，
        // 如果最后一次跳跃刚好到达了最后一个位置，那么遍历到最后一个位置的时候就会再次起跳，
        // 这是不允许的，因此不能遍历最后一个位置
        for (int i = 0; i < nums.length - 1; i++) {
            k = Math.max(k, i + nums[i]);
            // 到达上次跳跃能到达的右边界了
            if (i == end) {
                count++;
                end = k;  // 目前能跳到的最远位置变成了下次起跳位置的右边界
            }
        }
        return count;
    }


    // 二战dp

    /**
     * 判断当前位置i能否由前面的j个位置跳过来，并且能从当前j位置跳过i
     *
     * @param nums
     * @return
     */
    public boolean canJumpP(int[] nums) {
        boolean[] f = new boolean[nums.length];
        f[0] = true;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (f[j] && nums[j] + j >= i) {
                    f[i] = true;
                    break;
                }
            }
        }
        return f[nums.length - 1];
    }


    // 贪心
    public boolean canJumpP2(int[] nums) {
        int max = nums[0];
        int n = nums.length;
        for (int i = 1; i < n; i++) {
            //能否跳到当前位置
            if (max >= i) {
                // 更新可以跳到最远的距离
                max = Math.max(max, i + nums[i]);
                if (max > n - 1) {
                    return true;
                }
            } else {
                break;
            }
        }
        return false;
    }

    // 跳跃游戏II，二战,dp
    public int jump(int[] nums) {
        int[] f = new int[nums.length];
        Arrays.fill(f, Integer.MAX_VALUE);
        f[0] = 0;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] + j >= i) {
                    f[i] = Math.min(f[j] + 1, f[i]);
                }
            }
        }
        return f[nums.length - 1];
    }
}
